In a transmission between a source and a receiver, some transmission errors may occur. Error correcting codes can be used to detect and correct some of these errors. Low-Density Parity-Check (LDPC) Codes are a class of error correcting code: they are block codes (or equivalently parity-check codes) and are defined by a parity-check matrix H. They were introduced in 1963 by R. G. Gallager (in Gallager's Thesis, “Low-Density Parity-Check Codes”, 1963, MIT) in the case of LDPC codes over the Galois Field GF(2). The principle was generalized by Mackay in 1998 (in D. J. C Mackay, M. C. Davey, “Low Density Check Code over GF(q)”, Cavendish Laboratory, Cambridge, United Kingdom, 1998) over a Galois Field of higher cardinality, i.e. GF(rq) where r is a prime number. LDPC codes can be used in a variety of transmission systems, e.g. satellite communications, wireless transmissions, fiber optics, and a variety of storage media e.g. hard disk drive, optical disk, magnetic band. Examples of systems that use LDPC are DVB-S2, DMB-T (Chinese DVB Terrestrial standard), STiMi (Chinese DVB satellite standard), IEEE 802.11n and 802.16e.
An LDPC code is defined by a parity-check matrix H of size M rows by N columns, M being the number of constraints (corresponding check nodes) and N being the number of variables (estimated values of symbols of the code, represented by symbol nodes). A non-zero entry of the matrix at position (m,n) indicates that the variable vn participates in the constraint cm. Most newly standardized systems use a parity check matrix that is subdivided in blocks (matrices), called circulants. A circulant is either a zero-matrix (all elements 0) or based on an identity matrix. The circulants that are based on the identity matrix may be single diagonal (either the identity matrix itself or a rotated version of the identity matrix) or may have multiple diagonals. A so-called barrel shifter is used to rotate the variables, which are usually stored in the normal sequential sequence in a memory) to a position that is defined by rotation of the identity matrix. A state-of-the art, low-cost implementation is published in J. Dielissen et. al. “Low cost LDPC decoder for DVB-S2”, in IEEE Proceedings of DATE, 2006, hereinafter [Dielissen, DATE]. However, this architecture cannot solve LDPC codes containing “multiple diagonals”. Processing of multiple diagonals is clearly more complicated. US2005/0138519 A1 shows an architecture designed for dealing with multi-diagonal circulants. However, this architecture is not scalable towards cheap instantiations which do not need to solve the “multiple diagonals”.